package datastructure;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;

/**
 * Created with IntelliJ IDEA.
 * Description:
 *
 * @author lzy
 * @create 2019-11-07 下午2:31
 */
public class CountSort {
    /**
     * 计数排序
     *
     * @param array
     * @return
     */
    public static int[] countSort(int[] array) {
        // 得到数列的最大值
        int max = array[0];
        for (int i = 0; i < array.length; i++) {
            if (array[i] > max) {
                max = array[i];
            }
        }

        //2.根据数列最大值确定统计数组的长度
        int[] countArray = new int[max + 1];
        //3.遍历数列，填充统计数组
        for (int i = 0; i < array.length; i++) {
            countArray[array[i]]++;
        }
        //4.遍历统计数组，输出结果
        int index = 0;
        int[] sortedArray = new int[array.length];
        for (int i = 0; i < countArray.length; i++) {
            for (int j = 0; j < countArray[i]; j++) {
                sortedArray[index++] = i;
            }
        }

        return sortedArray;
    }

    /**
     * 改进版的计数排序
     *
     * @param array
     * @return
     */
    public static int[] countSort2(int[] array) {
        //得到最大数和最小数，并求出差值
        int max = array[0];
        int min = array[0];
        for (int i = 0; i < array.length; i++) {
            if (array[i] > max) {
                max = array[i];
            }
            if (array[i] < min) {
                min = array[i];
            }
        }
        int d = max - min;
        //2.创建统计数组并统计对应元素的个数
        int[] countArray = new int[d + 1];
        for (int i = 0; i < array.length; i++) {
            countArray[array[i] - min]++;
        }
        //3.统计数组做变形，后面的元素等于前面元素的和
        for (int i = 1; i < countArray.length; i++) {
            countArray[i] += countArray[i - 1];
        }
        //４.倒序遍历原始数组，从统计数组找到正确的位置，输出结果到数组
        int[] sortedArray = new int[array.length];
        for (int i = array.length - 1; i >= 0; i--) {
            sortedArray[countArray[array[i] - min] - 1] = array[i];
            countArray[array[i] - min]--;
        }
        return sortedArray;
    }

    /**
     * 桶排序
     *
     * @param array
     * @return
     */
    public static double[] bucketSort(double[] array) {
        //1.得到数列的最小值和最大值，并算出差值ｄ
        double max = array[0];
        double min = array[0];
        for (double v : array) {
            if (v > max) {
                max = v;
            }
            if (v < min) {
                min = v;
            }
        }
        double d = max - min;

        //2.初始化桶
        int bucketNum = array.length;
        ArrayList<LinkedList<Double>> bucketList = new ArrayList<>();
        for (int i = 0; i < bucketNum; i++) {
            bucketList.add(new LinkedList<>());
        }

        //3.遍历原始数组，将每个元素放入桶中
        for (int i = 0; i < array.length; i++) {
            int num = (int) ((array[i] - min) * (bucketNum - 1) / d);
            bucketList.get(num).add(array[i]);
        }

        //4.对每个桶内部进行排序
        for (int i = 0; i < array.length; i++) {
            //jdk底层采用了归并排序的优化版本
            Collections.sort(bucketList.get(i));
        }

        //5.输出全部元素
        double[] sortedArray = new double[array.length];
        int index = 0;
        for (LinkedList<Double> list : bucketList) {
            for (Double element : list) {
                sortedArray[index] = element;
                index++;
            }
        }

        return sortedArray;
    }

    public static void main(String[] args) {
        int[] array = {95, 94, 91, 98, 99, 90, 99, 93, 91, 92};
        int[] sortedArray = countSort2(array);
        System.out.println(Arrays.toString(sortedArray));


        double[] dArray = {4.12, 6.421, 0.0023, 3.0, 2.123, 8.122, 4.12, 10.09};
        final double[] sortArray = bucketSort(dArray);
        System.out.println(Arrays.toString(sortArray));
    }
}
